1. Field of the Invention
The invention relates to design of semiconductor chips. More specifically, the invention relates to a method and an apparatus for propagating tuples through a representation of a circuit design and use of propagated tuples to identify a point of convergence of signals clocked at different frequencies.
2. Related Art
FIG. 1A illustrates a circuit design in which signals Q1 and Q2 from two flip-flops 101 and 102 that are respectively clocked by signals ClkA and ClkB travel through a number of flip-flops that are clocked by yet another signal ClkC. In the circuit design of FIG. 1A, it is typical to include flip-flops 103-106 as “synchronizers” followed by additional flip-flops 107-112 as “pipeline stages.”
In such a circuit design, it is not easy to identify exactly where the signals Q1 and Q2 converge (or to identify whether or not they converge at all). Automatic identification of AND gate n100 (FIG. 1A) as a point of convergence of the two signals is useful in determining whether or not a sufficient number of flip-flops (clocked by signal ClkC) have been traversed. If the number of flip-flops that are traversed before convergence of signals Q1 and Q2 is less than a predetermined number (e.g. less than two flip-flops or three flip-flops), then metastability can occur.
Since metastability is to be avoided, currently there is a need to identify the sequential depth at which such signal convergence occurs in designs of integrated circuits (ICs), such as graphics chips that may contain millions of gates (e.g. 35 million gates). Conventional methods that have complexity on the order of N2 (where N is the number of gates) are unable to find points of signal convergence in a reasonable duration of time during circuit design, when such methods are executed in computers currently used for analyzing and simulating circuit designs, such as a Sun workstation.
U.S. Pat. Nos. 5,938,785, 6,567,961 and 5,650,938 are incorporated by reference herein in their entirety as background.
FIG. 1B illustrates another circuit design, wherein a sixteen bit bus 162 carries data from flip-flops 161 clocked by a first clock signal clkA to a First-In-First-Out (FIFO) memory 163 that is clocked by a second clock signal clkB. Note that for simplicity of the drawing, only one flip-flop 161 is shown on the left side of bus 162 and only one flip-flop is shown on the right side of bus 162, although it is to be understood that there are sixteen such flip-flops on each side of the bus. Moreover, FIFO 163 has sixteen flip-flops in each of several stages (although only two stages in the form of two flip-flops are shown in FIFO 163 of FIG. 1B).
In a circuit of the type illustrated in FIG. 1B as discussed above, it is common to include a Gray coder 170 clocked at clkA, followed by the following circuit elements that are clocked at clkB: synchronizers 172, a Gray decoder 173, and a state machine 174. The state machine 174 generates an enable signal that is used to enable FIFO 163 to latch a signal from data bus 162. Note that FIFO 163 is enabled by state machine 174 if in the current clock cycle only one single bit changes in the signal received by Gray decoder 173, as compared to the previous clock cycle. If more than one bit changes, then state machine 174 disables the FIFO 163 and the signal on bus 162 is not latched.
The just-described technique is known to minimize or even eliminate errors in transfer of data between the two clock domains (clocked by the respective signals clkA and clkB). However, when such circuitry is designed, it is possible for a circuit designer to fail to include one or more circuit elements, such as synchronizers 172 or some portion of state machine 174. The problem becomes acute when a prior art circuit design contains 100s or 1000s of buses that cross clock domains, such as bus 162. Hence, there is a need to automatically find such errors in circuit design during the design stage, i.e. before the circuit description is prepared into a netlist (for fabrication of an integrated circuit chip).